package a07_二叉树;

/**
 * <p>
 * a19_最大二叉树复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/19
 */
public class a19_最大二叉树复习2 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }

    private TreeNode traversal(int[] nums,int leftIdx,int rightIdx){
        if(leftIdx > rightIdx){
            return null;
        }
        int maxVal = Integer.MIN_VALUE;
        int maxIdx = 0;
        for (int i = leftIdx; i <= rightIdx; i++) {
            if(nums[i] > maxVal){
                maxVal = nums[i];
                maxIdx = i;
            }
        }

        TreeNode rootNode = new TreeNode(maxVal);
        rootNode.left = traversal(nums, leftIdx, maxIdx - 1);
        rootNode.right = traversal(nums, maxIdx + 1, rightIdx);
        return rootNode;
    }
}
